home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / graphic / jpegsrc4.zip / JQUANT2.C < prev    next >
C/C++ Source or Header  |  1992-11-04  |  43KB  |  1,164 lines
  1. /*
  2.  * jquant2.c
  3.  *
  4.  * Copyright (C) 1991, 1992, Thomas G. Lane.
  5.  * This file is part of the Independent JPEG Group's software.
  6.  * For conditions of distribution and use, see the accompanying README file.
  7.  *
  8.  * This file contains 2-pass color quantization (color mapping) routines.
  9.  * These routines are invoked via the methods color_quant_prescan,
  10.  * color_quant_doit, and color_quant_init/term.
  11.  */
  12.  
  13. #include "jinclude.h"
  14.  
  15. #ifdef QUANT_2PASS_SUPPORTED
  16.  
  17.  
  18. /*
  19.  * This module implements the well-known Heckbert paradigm for color
  20.  * quantization.  Most of the ideas used here can be traced back to
  21.  * Heckbert's seminal paper
  22.  *   Heckbert, Paul.  "Color Image Quantization for Frame Buffer Display",
  23.  *   Proc. SIGGRAPH '82, Computer Graphics v.16 #3 (July 1982), pp 297-304.
  24.  *
  25.  * In the first pass over the image, we accumulate a histogram showing the
  26.  * usage count of each possible color.  (To keep the histogram to a reasonable
  27.  * size, we reduce the precision of the input; typical practice is to retain
  28.  * 5 or 6 bits per color, so that 8 or 4 different input values are counted
  29.  * in the same histogram cell.)  Next, the color-selection step begins with a
  30.  * box representing the whole color space, and repeatedly splits the "largest"
  31.  * remaining box until we have as many boxes as desired colors.  Then the mean
  32.  * color in each remaining box becomes one of the possible output colors.
  33.  * The second pass over the image maps each input pixel to the closest output
  34.  * color (optionally after applying a Floyd-Steinberg dithering correction).
  35.  * This mapping is logically trivial, but making it go fast enough requires
  36.  * considerable care.
  37.  *
  38.  * Heckbert-style quantizers vary a good deal in their policies for choosing
  39.  * the "largest" box and deciding where to cut it.  The particular policies
  40.  * used here have proved out well in experimental comparisons, but better ones
  41.  * may yet be found.
  42.  *
  43.  * The most significant difference between this quantizer and others is that
  44.  * this one is intended to operate in YCbCr colorspace, rather than RGB space
  45.  * as is usually done.  Actually we work in scaled YCbCr colorspace, where
  46.  * Y distances are inflated by a factor of 2 relative to Cb or Cr distances.
  47.  * The empirical evidence is that distances in this space correspond to
  48.  * perceptual color differences more closely than do distances in RGB space;
  49.  * and working in this space is inexpensive within a JPEG decompressor, since
  50.  * the input data is already in YCbCr form.  (We could transform to an even
  51.  * more perceptually linear space such as Lab or Luv, but that is very slow
  52.  * and doesn't yield much better results than scaled YCbCr.)
  53.  */
  54.  
  55. #define Y_SCALE 2        /* scale Y distances up by this much */
  56.  
  57. #define MAXNUMCOLORS  (MAXJSAMPLE+1) /* maximum size of colormap */
  58.  
  59.  
  60. /*
  61.  * First we have the histogram data structure and routines for creating it.
  62.  *
  63.  * For work in YCbCr space, it is useful to keep more precision for Y than
  64.  * for Cb or Cr.  We recommend keeping 6 bits for Y and 5 bits each for Cb/Cr.
  65.  * If you have plenty of memory and cycles, 6 bits all around gives marginally
  66.  * better results; if you are short of memory, 5 bits all around will save
  67.  * some space but degrade the results.
  68.  * To maintain a fully accurate histogram, we'd need to allocate a "long"
  69.  * (preferably unsigned long) for each cell.  In practice this is overkill;
  70.  * we can get by with 16 bits per cell.  Few of the cell counts will overflow,
  71.  * and clamping those that do overflow to the maximum value will give close-
  72.  * enough results.  This reduces the recommended histogram size from 256Kb
  73.  * to 128Kb, which is a useful savings on PC-class machines.
  74.  * (In the second pass the histogram space is re-used for pixel mapping data;
  75.  * in that capacity, each cell must be able to store zero to the number of
  76.  * desired colors.  16 bits/cell is plenty for that too.)
  77.  * Since the JPEG code is intended to run in small memory model on 80x86
  78.  * machines, we can't just allocate the histogram in one chunk.  Instead
  79.  * of a true 3-D array, we use a row of pointers to 2-D arrays.  Each
  80.  * pointer corresponds to a Y value (typically 2^6 = 64 pointers) and
  81.  * each 2-D array has 2^5^2 = 1024 or 2^6^2 = 4096 entries.  Note that
  82.  * on 80x86 machines, the pointer row is in near memory but the actual
  83.  * arrays are in far memory (same arrangement as we use for image arrays).
  84.  */
  85.  
  86. #ifndef HIST_Y_BITS        /* so you can override from Makefile */
  87. #define HIST_Y_BITS  6        /* bits of precision in Y histogram */
  88. #endif
  89. #ifndef HIST_C_BITS        /* so you can override from Makefile */
  90. #define HIST_C_BITS  5        /* bits of precision in Cb/Cr histogram */
  91. #endif
  92.  
  93. #define HIST_Y_ELEMS  (1<<HIST_Y_BITS) /* # of elements along histogram axes */
  94. #define HIST_C_ELEMS  (1<<HIST_C_BITS)
  95.  
  96. /* These are the amounts to shift an input value to get a histogram index.
  97.  * For a combination 8/12 bit implementation, would need variables here...
  98.  */
  99.  
  100. #define Y_SHIFT  (BITS_IN_JSAMPLE-HIST_Y_BITS)
  101. #define C_SHIFT  (BITS_IN_JSAMPLE-HIST_C_BITS)
  102.  
  103.  
  104. typedef UINT16 histcell;    /* histogram cell; MUST be an unsigned type */
  105.  
  106. typedef histcell FAR * histptr;    /* for pointers to histogram cells */
  107.  
  108. typedef histcell hist1d[HIST_C_ELEMS]; /* typedefs for the array */
  109. typedef hist1d FAR * hist2d;    /* type for the Y-level pointers */
  110. typedef hist2d * hist3d;    /* type for top-level pointer */
  111.  
  112. static hist3d histogram;    /* pointer to the histogram */
  113.  
  114.  
  115. /*
  116.  * Prescan some rows of pixels.
  117.  * In this module the prescan simply updates the histogram, which has been
  118.  * initialized to zeroes by color_quant_init.
  119.  * Note: workspace is probably not useful for this routine, but it is passed
  120.  * anyway to allow some code sharing within the pipeline controller.
  121.  */
  122.  
  123. METHODDEF void
  124. color_quant_prescan (decompress_info_ptr cinfo, int num_rows,
  125.              JSAMPIMAGE image_data, JSAMPARRAY workspace)
  126. {
  127.   register JSAMPROW ptr0, ptr1, ptr2;
  128.   register histptr histp;
  129.   register int c0, c1, c2;
  130.   int row;
  131.   long col;
  132.   long width = cinfo->image_width;
  133.  
  134.   for (row = 0; row < num_rows; row++) {
  135.     ptr0 = image_data[0][row];
  136.     ptr1 = image_data[1][row];
  137.     ptr2 = image_data[2][row];
  138.     for (col = width; col > 0; col--) {
  139.       /* get pixel value and index into the histogram */
  140.       c0 = GETJSAMPLE(*ptr0++) >> Y_SHIFT;
  141.       c1 = GETJSAMPLE(*ptr1++) >> C_SHIFT;
  142.       c2 = GETJSAMPLE(*ptr2++) >> C_SHIFT;
  143.       histp = & histogram[c0][c1][c2];
  144.       /* increment, check for overflow and undo increment if so. */
  145.       /* We assume unsigned representation here! */
  146.       if (++(*histp) == 0)
  147.     (*histp)--;
  148.     }
  149.   }
  150. }
  151.  
  152.  
  153. /*
  154.  * Now we have the really interesting routines: selection of a colormap
  155.  * given the completed histogram.
  156.  * These routines work with a list of "boxes", each representing a rectangular
  157.  * subset of the input color space (to histogram precision).
  158.  */
  159.  
  160. typedef struct {
  161.     /* The bounds of the box (inclusive); expressed as histogram indexes */
  162.     int c0min, c0max;
  163.     int c1min, c1max;
  164.     int c2min, c2max;
  165.     /* The number of nonzero histogram cells within this box */
  166.     long colorcount;
  167.       } box;
  168. typedef box * boxptr;
  169.  
  170. static boxptr boxlist;        /* array with room for desired # of boxes */
  171. static int numboxes;        /* number of boxes currently in boxlist */
  172.  
  173. static JSAMPARRAY my_colormap;    /* the finished colormap (in YCbCr space) */
  174.  
  175.  
  176. LOCAL boxptr
  177. find_biggest_color_pop (void)
  178. /* Find the splittable box with the largest color population */
  179. /* Returns NULL if no splittable boxes remain */
  180. {
  181.   register boxptr boxp;
  182.   register int i;
  183.   register long max = 0;
  184.   boxptr which = NULL;
  185.   
  186.   for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) {
  187.     if (boxp->colorcount > max) {
  188.       if (boxp->c0max > boxp->c0min || boxp->c1max > boxp->c1min ||
  189.       boxp->c2max > boxp->c2min) {
  190.     which = boxp;
  191.     max = boxp->colorcount;
  192.       }
  193.     }
  194.   }
  195.   return which;
  196. }
  197.  
  198.  
  199. LOCAL boxptr
  200. find_biggest_volume (void)
  201. /* Find the splittable box with the largest (scaled) volume */
  202. /* Returns NULL if no splittable boxes remain */
  203. {
  204.   register bo